/**
 *
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 这题有组合的思路, 但还是有点不一样的, 就是要按照顺序来写
 * 就像我们一开始分为一个字符, 然后再从这个字符向后遍历, 继续
 * 寻找满足总 这个字符后面开始向后的回文串, 单个字符肯定是满足条件的
 * 所以重点事后面的多位字符回文串, 找到了自然会加入 path 然后继续
 * 深搜
 * 这里还可以使用 dp 存储满足条件的回文串, 减少时间复杂度
 * 时间复杂度 : O(2 ^ n)
 * 空间复杂度 : O(n ^ 2)
 */

public class Main {

    // 定义全局变量
    int n;
    List<List<String>> res;
    List<String> path;
    boolean[][] dp;

    public List<List<String>> partition(String s) {

        // 初始化
        n = s.length();
        res = new ArrayList<>();
        path = new ArrayList<>();
        dp = new boolean[n][n];

        // dp
        for (int right = 0; right < n; right++) {
            for (int left = 0; left <= right; left++) {
                if (s.charAt(left) == s.charAt(right)
                        && (right - left <= 2 || dp[left + 1][right - 1])) {
                    dp[left][right] = true;
                }
            }
        }

        dfs(s, 0);
        return res;
    }

    public void dfs(String s, int index) {

        // 出口
        if (index == n) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 从 index 开始找回文串
        for (int i = index; i < n; i++) {
            if (dp[index][i]) {

                // 找到加入
                path.add(s.substring(index, i + 1));

                // 继续向后找
                dfs(s, i + 1);

                // 回复现场
                path.remove(path.size() - 1);
            }
        }
    }
}